#include "InterviewLink.h"
#include "LinkList.h"
//逆序打印单链表
void ReversePrintLinkList(LinkNode *head)
{
    if(NULL==head)
    {
        return;
    }
    if(head->next!=NULL)
    {
    ReversePrintLinkList(head->next);
    }
    printf("[%c] ",head->data);
}
//不允许遍历链表，在pos位置之前进行插入
void Swap(char *a,char *b)
{
    char tmp=*a;
    *a=*b;
    *b=tmp;
}
void InsertFrontLinkList(LinkNode **head,LinkNode *pos,LinkListType value)
{
    if(NULL==head||NULL==pos)
    {
        return;
    }
    LinkNode *new_node =LinkNodeCreate(value);
    if(NULL==*head)
    {
        *head=new_node;
        return;
    }
    new_node->next=pos->next;
    pos->next=new_node;
    Swap(&pos->data,&new_node->data);
}
//单链表的逆置（1）
void LinkListReverse_1(LinkNode **head)
{
    if(NULL==head)
    {
        return;
    }
    if(NULL==*head)
    {
        return;
    }
    LinkNode *cur=*head;
    LinkNode *Next=cur->next;
    while(Next!=NULL)
    {
        cur->next=Next->next;
        Next->next=*head;
        *head=Next;
        Next=cur->next;
    }
}
//链表的逆置（2）
void LinkListReverse_2(LinkNode **head)
{
    if(NULL==head)
    {
        return;
    }
    if(NULL==*head)
    {
        return;
    }
    LinkNode *cur=*head;
    LinkNode *pre=NULL;
    LinkNode *Next=cur->next;
    while(Next!=NULL)
    {
        cur->next=pre;
        pre=cur;
        cur=Next;
        Next=Next->next;
    }
    cur->next=pre;
    *head=cur;
}
//单链表的冒泡排序
void LinkListBubbleSort(LinkNode *head)
{
    if(NULL==head)
    {
        return;
    }
    LinkNode *count=head;
    LinkNode *cur=head;
    LinkNode *end=NULL;
    for(count=head;count->next!=NULL;count=count->next)
    {
        for(cur=head;cur->next!=end;cur=cur->next)
        {
            if(cur->data>cur->next->data)
            {
                Swap(&cur->data,&cur->next->data);
            }
        }
        end=cur;
    }
}
//将两个有序链表合并为一个有序链表
LinkNode * LinkListMerge(LinkNode *head1,LinkNode *head2)
{
    LinkNode *cur1=head1;
    LinkNode *cur2=head2;
    LinkNode *new_head=NULL;
    LinkNode *new_tail=NULL;
    while(NULL!=cur1&&NULL!=cur2)
    {
            if(cur1->data<cur2->data)
            {
                if(new_head==NULL)
                {
                    new_head=new_tail=LinkNodeCreate(cur1->data);
                }
                else
                {
                    new_tail->next=LinkNodeCreate(cur1->data);
                    new_tail=new_tail->next;
                }
                cur1=cur1->next;
            }
            else
            {
                if(NULL==new_head)
                {
                    new_head=new_tail=LinkNodeCreate(cur2->data);
                }
                else
                {
                    new_tail->next=LinkNodeCreate(cur2->data);
                    new_tail=new_tail->next;
                }
                cur2=cur2->next;
            }
    }
    while(cur1!=NULL)
    {
        if(new_head==NULL)
          {
              new_head=new_tail=LinkNodeCreate(cur1->data);
              continue;
          }
        new_tail->next=LinkNodeCreate(cur1->data);
        new_tail=new_tail->next;
        cur1=cur1->next;
    }
    while(cur2!=NULL)
    {
        if(new_head==NULL)
          {
              new_head=new_tail=LinkNodeCreate(cur1->data);
              continue;
          }
        new_tail->next=LinkNodeCreate(cur2->data);
        new_tail=new_tail->next;
        cur2=cur2->next;
    }
    return new_head;
}
//找到倒数第k个节点
LinkNode *LinkListFindLastKNode(LinkNode *head,size_t k)
{
    if(NULL==head)
    {
        return NULL;
    }
    LinkNode *fast=head;
    LinkNode *slow=head;
    size_t step=k-1;
    for(step=1;step<k;step++)
    {
        if(fast==NULL)
        {
            break;
        }
        fast=fast->next;
    }
    if(fast==NULL)
    {//说明k大于链表长度
        return NULL;
    }
    for(;fast->next!=NULL;fast=fast->next,slow=slow->next)
    {
        ;
    }
    return slow;
}
//删除倒数第k个节点
void LinkListEraseLastKNode(LinkNode **head,size_t k)
{
    if(NULL==head)
    {
        return;
    }
    if(NULL==*head)
    {
        return;
    }
    LinkNode *fast=*head;
    LinkNode *slow=*head;
    size_t i=0;
    for(i=1;i<k;i++)
    {
        if(fast==NULL)
        {
            break;
        }
        fast=fast->next;
    }
    if(fast==NULL)
    {
        return;
    }
    LinkNode *slow_pre=NULL;
    while(fast->next!=NULL)
    {
        fast=fast->next;
        slow_pre=slow;
        slow=slow->next;
    }
    if(slow_pre==NULL)
    {
        *head=(*head)->next;
        LinkNodeDestroy(slow);
    }
    else
    {
        slow_pre->next=slow->next;
        LinkNodeDestroy(slow);
    }
}
//判断链表是否带环，是的话返回1,否则就返回0
int LinkListHasCycle(LinkNode *head)
{
    LinkNode *fast=head;
    LinkNode *slow=head;
    while(fast!=NULL)
    {
        if(fast->next==NULL)
        {
            return 0;
        }
        fast=fast->next->next;
        slow=slow->next;
        if(slow==fast)
        {
            return 1;
        }
    }
    return 0;
}
//如果链表带环，求出环的长度
size_t LinkListGetCycleSize(LinkNode *head)
{
    size_t len=0;
    LinkNode *fast=head;
    LinkNode *slow=head;
    while(fast!=NULL)
    {
        if(fast->next==NULL)
        {
            return 0;
        }
        fast=fast->next->next;
        slow=slow->next;
        if(slow==fast)
        {
            fast=fast->next;
            ++len;
            while(fast!=slow)
            {
                fast=fast->next;
                ++len;
            }
            return len;
        }
    }
    return (size_t)-1;
}
//如果链表带环，求出环的出口
LinkNode *LinkListGetCycleEntry(LinkNode *head)
{
    if(NULL==head)
    {
        return NULL;
    }
    size_t len=0;
    LinkNode *fast=head;
    LinkNode *slow=head;
    while(fast!=NULL)
    {
        if(fast->next==NULL)
        {
            return NULL;
        }
        fast=fast->next->next;
        slow=slow->next;
        if(slow==fast)
        {
            fast=fast->next;
            ++len;
            while(fast!=slow)
            {
                fast=fast->next;
                ++len;
            }
            break;
        }
    }
    slow=fast=head;
    size_t i=0;
    for(i=0;i<len;i++)
    {
        fast=fast->next;
    }
    while(fast!=slow)
    {
        fast=fast->next;
        slow=slow->next;
    }
    return slow;
}
//两个不带环的链表判断是否相交
LinkNode *LinkListHasCrosses(LinkNode *head1,LinkNode *head2)
{
    if(NULL==head1||NULL==head2)
    {
        return NULL;
    }
    LinkNode *cur1=head1;
    LinkNode *cur2=head2;
    size_t len1=LinkListSize(head1);
    size_t len2=LinkListSize(head2);
    size_t step=0;
    if(len1>len2)
    {
        step=len1-len2;
        size_t i=0;
        for(i=0;i<step;i++)
        {
            cur1=cur1->next;
        }
    }
    else
    {
        step=len2-len1;
        size_t i=0;
        for(i=0;i<step;i++)
        {
            cur2=cur2->next;
        }
    }
    while(cur1!=NULL&&cur2!=NULL)
    {
        if(cur1==cur2)
        {
            return cur1;
        }
        cur1=cur1->next;
        cur2=cur2->next;
    }
    return NULL;
}
//两个可能带环的链表判断是否相交
int LinkListHasCrossesWithCycle(LinkNode *head1,LinkNode *head2)
{
    if(NULL==head1||NULL==head2)
    {
        return 0;
    }
    LinkNode *cur1=head1;
    LinkNode *cur2=head2;
    int ret_1=LinkListHasCycle(head1);
    int ret_2=LinkListHasCycle(head2);
    if(ret_1==0&&ret_2==0)
    {
    size_t len1=LinkListSize(head1);
    size_t len2=LinkListSize(head2);
        size_t step=0;
        if(len1>len2)
        {
            step=len1-len2;
            size_t i=0;
            for(i=0;i<step;i++)
            {
                cur1=cur1->next;
            }
        }
        else
        {
            step=len2-len1;
            size_t i=0;
            for(i=0;i<step;i++)
            {
                cur2=cur2->next;
            }
        }
        while(cur1!=NULL&&cur2!=NULL)
        {
            if(cur1==cur2)
            {
                return 1;
            }
            cur1=cur1->next;
            cur2=cur2->next;
        }
        return 0;

    }
    else
        if(ret_1==1&&ret_2==1)
        {//两个链表均带环的话，就出环的入口开始判断
        
            LinkNode *entry_1=LinkListGetCycleEntry(head1);
            LinkNode *entry_2=LinkListGetCycleEntry(head2);
            if(entry_1==entry_2)
            {
                return 1;
            }
            else
            {
                LinkNode *cur=entry_2->next;
                while(entry_2!=cur)
                {
                    if(cur==entry_1)
                    {
                        return 1;
                    }
                    cur=cur->next;
                }
                return 0;
            }
        }
    else
    {//一个带环，一个不带环的情况
        return 0;
    }
}
